/**
 * @Classname HeapSort 堆排序：大顶堆和小顶堆
 * @Description 利用堆这种数据结构做排序,是一种选择排序时间复杂度为O（nlogn）
 * 将待排序的序列构成一个大顶堆，最大指就为堆顶的根节点，再将其与末尾元素进行交换，末尾就为最大值了，
 * 将剩余元素重新构成一个堆，得到次大值，最终得到一个有序序列
 * @Date 2021/12/3 15:35
 * @Created K024851
 */
public class HeapSort {
    public static void main(String[] args) {
        int arr[] = new int[80000];
        for (int i=0;i<80000;i++){
            arr[i] = (int) Math.random()*80000;
        }
        System.out.println("排序前");

        heapSort(arr);
        System.out.println("排序后");
    }

    public static void  heapSort(int arr[]){
        int temp =0;
        System.out.println("堆排序");

        for (int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //将最大的元素放到数组末端

        for(int j= arr.length-1;j>0;j--){
            temp =arr[j];
            arr[j] =arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }
    }
    //将一个数组（二叉树）调整为一个大顶堆
    public static void adjustHeap(int arr[],int i,int length){
        int temp = arr[i];
        for (int k = i*2+1;k<length;k=k*2+1){
            if (k+1<length && arr[k]<arr[k+1]){
                k++;
            }
            if (arr[k]>temp){
                arr[i] =arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i] = temp;
    }
}
